package 中等.搜索.广度优先搜索;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。
 * 岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。
 * grid 中 恰好存在两座岛 。
 * 你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。
 * 返回必须翻转的 0 的最小数目。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shortest-bridge
 */
public class 最短的桥_934 {

    public static void main(String[] args) {

        int[][] grid = {{0, 1}, {1, 0}};
        System.out.println(new 最短的桥_934().shortestBridge(grid));

    }

    private int[][] direction = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    /**
     * 深度优先搜索找到第一个岛屿全部节点
     * 广度优先搜索第一个岛屿到第二个岛屿的最短桥
     *
     * @param grid
     * @return
     */
    public int shortestBridge(int[][] grid) {
        Deque<int[]> queue = new ArrayDeque<>();
        // 找到第一个岛屿，将其加入队列
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    dfs(i, j, grid, queue);
                    // 外层循环也需要退出
                    i = grid.length;
                    break;
                }
            }
        }

        int count = -1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            count++;
            while (size-- > 0) {

                int[] curNode = queue.pollFirst();
                for (int[] direct : direction) {
                    int nextI = curNode[0] + direct[0];
                    int nextJ = curNode[1] + direct[1];

                    if (nextI >= 0 && nextI < grid.length &&
                            nextJ >= 0 && nextJ < grid[0].length) {
                        if (grid[nextI][nextJ] == 1) {
                            return count;
                        } else if (grid[nextI][nextJ] == 0) {
                            queue.addLast(new int[]{nextI, nextJ});
                        }
                        grid[nextI][nextJ] = -1;
                    }
                }
            }
        }

        return count;
    }

    private void dfs(int i, int j, int[][] grid, Deque<int[]> queue) {
        queue.addLast(new int[]{i, j});
        grid[i][j] = -1;

        for (int[] direct : direction) {
            int nextI = i + direct[0];
            int nextJ = j + direct[1];

            if (nextI >= 0 && nextI < grid.length &&
                    nextJ >= 0 && nextJ < grid[0].length &&
                    grid[nextI][nextJ] == 1) {

                dfs(nextI, nextJ, grid, queue);
            }
        }
    }

}
